package exercises.newcoder.solution;

/**
 * <a href="https://www.nowcoder.com/practice/c159db5028034aa595043a1a220a62dd?tpId=202&&tqId=38723&rp=1&ru=/activity/oj&qru=/ta/code-written-high/question-ranking">
 * WC14 包围区域</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 现在有一个仅包含‘X’和‘O’的二维板，请捕获所有的被‘X’包围的区域
 * 捕获一个被包围区域的方法是将被包围区域中的所有‘O’变成‘X’
 * <p>
 * 例如
 * <pre>{@code
 * X X X X
 * X O O X
 * X X O X
 * O X X X
 *  }</pre>
 * 执行完你给出的函数以后，这个二维板应该变成：
 * <pre>{@code
 * X X X X
 * X X X X
 * X X X X
 * O X X X
 *  }</pre>
 *
 * @author or2
 * @date 2021年09月25日 时间: 14:45
 */
public class WC14 {
    public void solve(char[][] board) {
        int col = board.length;
        if (col == 0) {
            return;
        }
        int row = board[0].length;

        for (int i = 0; i < row; i++) {
            dfs(board, 0, i);
            dfs(board, col - 1, i);
        }
        for (int i = 0; i < col; i++) {
            dfs(board, i, 0);
            dfs(board, i, row - 1);
        }

        for (char[] chars : board) {
            for (int i = 0; i < chars.length; i++) {
                if (chars[i] == '.') {
                    chars[i] = 'O';
                } else if (chars[i] == 'O') {
                    chars[i] = 'X';
                }
            }
        }
    }

    private void dfs(char[][] board, int col, int row) {
        if (board[col][row] == 'X' || board[col][row] == '.')
            return;

        board[col][row] = '.';

        if (col > 0)
            dfs(board, col - 1, row);
        if (col < board.length - 1)
            dfs(board, col + 1, row);
        if (row > 0)
            dfs(board, col, row - 1);
        if (row < board[0].length - 1)
            dfs(board, col, row + 1);
    }
}
